home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Technotools
/
Technotools (Chestnut CD-ROM)(1993).ISO
/
lang_oth
/
solvlog
/
solvlog.pro
next >
Wrap
Text File
|
1987-02-24
|
11KB
|
267 lines
/*
USING TURBO PROLOG TO SOLVE LOGIC PROBLEMS
BY: GARRY J. VASS (72307,3311)
INTRODUCTION
------------
A "logic problem" is a type of exercise wherein a solution is
arrived at through a process of deduction and elimination. Most
commonly, logic problems appear as a brief statement (used to
identify the dimensions and boundaries) followed by a set of
clues. The clues usually fall into four major categories:
1. Dead giveaways, for example, Mary rode the red horse;
2. Eliminations, for example, Sally did not ride the
red horse, both Phillipe and Jones rode the 9:45 train, etc.;
3. Upper/lower boundaries (actually a type of elimination),
for example, John was not the first to arrive,
Bill paid more than Jack, etc.; and
4. "Sneakies" (a more subtle elimination), for example,
the person who ate veal dropped her purse, the person
who drank white wine said he never ate radishes, etc.
Using clues such as these, it is possible to arrive at a unique
solution.
I find that these problems have been somewhat helpful in learning
TURBO PROLOG (and believe me, I openly concede that I am a mere
beginner), and the purpose of this file is to share my findings
with other beginners and to solicit tutelage from the more advanced
PROLOG wizards.
I am most interested in hearing from both sides. I can be reached
via message at box 72307,3311 on Compuserve, at the Omegammon BBS
(201 - 653 - 3893), or the Police Station BBS (which supports
a TURBO PROLOG SIG at 201 - 963 - 3115).
NOTES
-----
Try the problem using pencil and paper first. It makes the ANALYSIS
discussion more lucid.
In interactive mode, use the "final" goal. This takes an astounding
amount of time to unify (2 - 3 minutes). My TURBO PASCAL logic problem
solver (which uses boolean arrays and recursion and is infinitely
more generalized) zips out this solution in about 5 seconds.
I originally started using list structures, but threw those
overboard because I was unable to program the "deduction through
elimination" that was needed.
If you are really into it, play with the compiler options.
STATEMENT OF THE PROBLEM
------------------------
Three friends went to a flea market together,
Ron, Garry, and John (whose last names are Vass, Ross,
and Clark - but not in that order). They returned with
a monitor, a modem, and a keyboard having paid $150, $200,
and $250 (again, no special order). Using the clues below,
please provide the correct name, item, and cost relationships.
NOTE: These were highly specialized items, so any pre-assumptions
regarding for example, a monitor being more expensive than
a keyboard, are unwarranted.
CLUES
-----
1. The monitor was the cheapest item.
2. ron did not purchase the modem.
3. garry spent less than ross (who did not purchase
the keyboard).
4. clark paid $250.
ANALYSIS
--------
There are four dimensions: first name, last name, item, and cost.
These appear in the DOMAIN section as firstname, lastname, itemname,
and costname respectively. The first three are nominal symbols. Cost
has comparison and boundary aspects (less than, greater than, etc.),
so it is defined as an integer.
We are given explicit information about
1. item and cost (clue 1);
2. first name and item (clue 2);
3. first name and last name, rather that
garry is not ross (clue 3);
4. last name and item (clue 3);
5. first name and cost (clue 3); and
6. last name and cost(clue 3 and clue 4).
These readily translate into six rules, which are
listed in the PREDICATES section as rule1, rule2,
rule3, rule4, rule5, and rule6 respectively.
A valid first name/last name/item/cost combination (or SET) must
satisfy all of the following conditions simultaneously:
1. the first name must be valid (e.i. within those
known to the problem - no marvins or henrys for example);
2. the last name must be valid;
3. the item name must be valid;
4. the cost must be valid; and
5. none of the six rules are violated.
The predicate for accomplishing this is the SET predicate.
The problem is now reduced to finding three valid sets at one
time in such a way that the contents of each set are unique.
In other words, we want three valid sets wherein the monitor
appears only once, the modem appears only once, the keyboard
appears only once, ron appears only once, and so on. To help
get us there, the "alldifferent" and "allsets" predicates are used.
Use "TRACE" to follow why the "alldifferent" predicates are needed.
The "final" predicate simply formats the program's conclusions.
*/
/* ---------- mydirs.inc ------------- */
/* nowarnings */
/* trace */
/* check_determ */
/* check_cmpio */
/*----------- end of mydirs.inc -------*/
domains
firstname = symbol
lastname = symbol
itemname = symbol
costname = integer
predicates
first(firstname)
last(lastname)
item(itemname)
cost(costname)
rule1(itemname, costname)
rule2(firstname, itemname)
rule3(firstname, lastname)
rule4(lastname, itemname)
rule5(firstname, costname)
rule6(lastname, costname)
set(firstname, lastname, itemname, costname)
alldifferentfirst(firstname, firstname, firstname)
alldifferentlast(lastname, lastname, lastname)
alldifferentitem(itemname, itemname, itemname)
allsets(firstname,firstname,firstname,
lastname, lastname, lastname,
itemname, itemname, itemname,
costname, costname, costname)
final
clauses
first(X) if /* The first, last, item, and cost */
X = "garry" or /* predicates are used to initialize */
X = "john" or /* the symbols and to prevent unbound */
X = "ron". /* variables in the other clauses. */
last(X) if
X = "clark" or
X = "ross" or
X = "vass".
item(X) if
X = "modem" or
X = "monitor" or
X = "keyboard".
cost(X) if
X = 150 or
X = 200 or
X = 250.
alldifferentfirst(A,B,C) if /* The alldifferent predicates guard */
A <> B and /* against getting non-unique solutions */
A <> C and /* */
B <> C. /* Try "commenting them out" to see */
alldifferentlast(A,B,C) if /* what I mean by "non-uniqueness" */
A <> B and
A <> C and /* A deterministic condition is achieved by */
B <> C. /* using alldifferent for any three of the */
alldifferentitem(A,B,C) if /* four dimensions. So there is no need for*/
A <> B and /* an "alldifferentcost" predicate */
A <> C and
B <> C.
allsets(F1,F2,F3,L1,L2,L3,R1,R2,R3,C1,C2,C3) if
first(F1) and
first(F2) and /* The allsets predicate is used as a mechanism */
first(F3) and /* to provide the "elimination trick" and */
last(L1) and /* to arrive at a simultaneous, nonredundant*/
last(L2) and /* solution. */
last(L3) and
item(R1) and /* It succeeds if three sets can be derived */
item(R2) and /* at once. */
item(R3) and
cost(C1) and
cost(C2) and
cost(C3) and
alldifferentfirst(F1,F2,F3) and
alldifferentlast(L1,L2,L3) and
alldifferentitem(R1,R2,R3) and
set(F1,L1,R1,C1) and
set(F2,L2,R2,C2) and
set(F3,L3,R3,C3).
set(First, Last, Item, Cost) if /* The set predicate is used to */
first(First) and /* collect a set of discrete first */
last(Last) and /* name/last name/item/cost combina-*/
item(Item) and /* tions according to the seven */
cost(Cost) and /* rules inferred in the problem */
rule1(Item,Cost) and /* statement. */
rule2(First,Item) and /* */
rule3(First,Last) and /* */
rule4(Last,Item) and /* */
rule6(Last,Cost) and /* */
rule5(First,Cost). /* */
rule1(monitor,150) if !. /* Rule 1 represents everything */
rule1(modem,_). /* known about what an item costs, namely */
rule1(keyboard,_). /* that the monitor costs 150 and other items */
/* cost something. */
rule2(ron,Item) if /* Rule 2 represents everything known */
Item <> "modem" and !. /* about a combination of first names */
rule2(garry,_). /* and items: ron did not take the */
rule2(john,_). /* modem and the others took something. */
rule3(garry,X) if /* Rule 3 represents everything known about */
X <> "ross" and !. /* a full name: garry's surname is not ross*/
rule3(john,_). /* and the others have a surname. */
rule3(ron,_). /* */
rule4(ross,Item) if /* Rule 4 represents everything known about */
Item <> "keyboard" and !. /* a last name/item combination: ross did */
rule4(clark,_). /* not take the keyboard, and the others took*/
rule4(vass,_). /* something. */
rule5(garry,X) if /* Rule 5 represents what is known about */
rule6(ross,Y) and /* first name/cost combinations: garry */
Y > 150 and /* paid less than ross (hence less than */
X < 250 and /* the maximum), and the others paid */
X < Y and /* something. */
!.
rule5(john,_).
rule5(ron,_).
rule6(clark,250) if !. /* Rule 6 represents what is known about */
rule6(ross,Cost) if /* last name/cost combinations: clark */
cost(Cost) and /* paid 250, ross paid more than 150, and */
Cost > 150 and !. /* vass paid something. */
rule6(vass,_). /* NOTE: poor vass is unbound here */
final if
time(Starthours, Startminutes, Startseconds,Starthundreds) and
nl and
write("Beginning at ",Starthours,":",Startminutes,":",Startseconds,":",Starthundreds) and
nl and
allsets(F1,F2,F3,L1,L2,L3,R1,R2,R3,C1,C2,C3) and
write(F1," ",L1," purchased a ",R1," for $",C1) and nl and
write(F2," ",L2," purchased a ",R2," for $",C2) and nl and
write(F3," ",L3," purchased a ",R3," for $",C3) and nl and
time(Endhours,Endminutes,Endseconds,Endhundreds) and
write("Ending at ",Endhours,":",Endminutes,":",Endseconds,":",Endhundreds) and
nl.
/*
goal
final.
*/